# -*- coding: utf-8 -*-
"""
Created on Mon Sep 21 21:00:30 2020

@author: Administrator
"""

'''
Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: nums = [1,2,3]
Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]
'''


class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        '''
        20200921--李运辰
        多看一下这种思路
        '''
        ans = []
        '''1,2,3'''
        
        '''
        ans=[]
        
        bt([],[1,2,3],t)
        ans=[[]]
        bt([1],[2,3],t)
        ans=[[1]]
        bt([1,2],[3],t)
        ans=[[1],[1,2]]
        bt([1,2,3],[],t)
        ans=[[1],[1,2],[1,2,3]]
        bt([1,2],[],f)
        ans=[[1],[1,2],[1,2,3]]
        bt([1],[3],f)
        bt([1,3],[],t)
        ans=[[1],[1,2],[1,2,3],[1,3]]
        bt([1],[],f)
        bt([],[2,3],f)
        bt([2],[3],t)
        ans=[[1],[1,2],[1,2,3],[1,3],[2]]
        bt([2,3],[],t)
        ans=[[1],[1,2],[1,2,3],[1,3],[2],[2,3]]
        bt([2],[],f)
        bt([],[3],f)
        bt([3],[],t)
        ans=[[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]
        bt([],[],f)
        
        '''
        def backtrack(s,nums,flag):
            if flag: ans.append(s)
            if not nums: return
            backtrack(s+[nums[0]],nums[1:],True)
            backtrack(s,nums[1:],False)
        backtrack([],nums,True)
        return ans
        
        